1. Field of the Invention
The present invention is related to communications-satellite network control. More particularly, it is related to channel allocation in multiple-satellite communication systems.
2. Discussion of Related Art
Terrestrial cellular communication systems are well known. Multiple Satellite communication systems complement terrestrial cellular communication systems to augment traffic handling capacity and service areas where wire or cellular networks have not reached. Satellite systems came into existence in response to the need for efficient and economical mobile communications. In general, the satellites act as a transponder, or xe2x80x9cbent pipexe2x80x9d, receiving ground based transmissions from one location and beaming the repeated transmission back down to another location after amplification and frequency shifting, as is discussed in U.S. Pat. No. 5,448,623, incorporated herein by reference in its entirety.
The basic principles of ground-linked cellular network operations are similar to those of the satellite-linked cellular networks. In both types of networks, a broadcast link is shared by all user terminals for network administration purposes. Each base station in a ground-cellular network has its own distinctive signal link for this purpose, serving as a xe2x80x9cbeaconxe2x80x9d that mobile user terminals detect as they move into that base station""s coverage area. The analog cellular radio system assigns channels using a frequency reuse pattern. These channel allocations require base stations for each frequency. A multiple satellite system provides channels through use of electronics on-board the spacecraft.
Mobile users initially find and select a cellular channel by searching for the strongest administrative pilot signals sent by nearby gateways as beacons. When the cellular network connects a user""s call, however, that call is assigned to its own individual circuit. Each satellite in a satellite-cellular network acts as a transponder between the network and its users, repeating whatever signal it receives and beaming the repeated signal back down to earth. Many satellite transponders pass the user""s call along like a simple xe2x80x9cbent pipexe2x80x9d would, providing only amplification and carrier-frequency translation.
Each satellite-cellular call is carried by a circuit made up of two-way links between a user and the satellite, and between the satellite and a gateway that links the satellite into ground-based communications networks as well as other satellite links. Cellular networks use three basic multiplexing techniques: Frequency-Division Multiple Access (FDMA); Code-Division Multiple Access (CDMA); and synchronous or asynchronous Time-Division Multiple Access (TDMA). The individual links will be pairs of carrier frequencies, pairs of CDMA tone or keycode references, or pairs of TDMA time-slice sequences or digitally-addressed packets.
In CDMA ground-cellular networks, only one fixed-bandwidth channel frequency need be assigned to each individual base station, since that channel is then multiplexed using spread-spectrum techniques that incorporate individual links into the channels carrier-frequency band using respective clock or keycode signals. For example the xe2x80x9c128-Aryxe2x80x9d Walsh-spreading codes can define 128 different spread-spectrum links per channel. Thus CDMA encoding can use its portion of the spectrum efficiently, but the frequencies it uses must all be contiguous.
In satellite-cellular networks, individual gateways characteristically support a much larger number of users than individual ground-cellular base stations. Therefore CDMA satellite networks require even more bandwidth than CDMA ground networks, making the use of non-contiguous frequencies in hybrid FDMA/CDMA networks"" over-all bandwidth particularly advantageous for satellite-cellular networks. In hybrid FDMA/CDMA multiplexing, each FDMA channel is a separate CDMA encoding system.
Wide bands of contiguous carrier frequencies are available within the present world-wide spectrum allocation plan above 20 Ghz. However, lower, L-band and S-band frequencies between 1.61 GHz and 2.5 GHz, and C-band frequencies between 5 GHz and 7.075 GHz, are more advantageous for satellite-cellular operations. These frequencies are less sensitive to the attenuation and cross-polarization interference effects of rain and other atmospheric conditions encountered in the 1414 km low earth orbits used for satellite-cellular communications links. Thus the hybrid FDMA/CDMA coding is particularly advantageous as a means of increasing the link capacity of satellite-cellular networks at the preferred, lower end of the spectrum.
On the other hand, although CDMA encoding theoretically provides efficient use of the spectrum, the hybrid CDMA links within each FDMA channel are xe2x80x9csoftxe2x80x9d. That is, although a given number of links can be encoded by a given spread spectrum technique, in theory, some lesser number will be usable in practice. It should be noted that the xe2x80x9cspectral efficiencyxe2x80x9d of a network is the number of calls that can be linked, relative to the maximum possible number of links within the portion of the spectrum that is being used in a given area.
The operational CDMA link-capacity of the FDMA channels in these hybrid systems is affected by path gain, co-channel interference between FDMA channels and CDMA self-interference within one FDMA channel, among other things. Moreover, the usable link-capacity of each satellite-cellular channel is further reduced and complicated by the link diversity required by satellite motion and by satellite battery-power constraints.
These constraints introduce uncertainty into the allocation of CDMA links in response to user demand. For example, even for a simple three-gateway region having only two satellites in view, the calculation of actual CDMA link capacity for one FDMA channel consumes two weeks of computing time on a high performance computer system. Uncertainty about the usable capacity of an FDMA channel can result in under-utilization, and so, can impair the actual, attainable spectral efficiency of FDMA/CDMA networks.
Several satellite-cellular networks using digitally-addressed TDMA packets similar to those used in conventional fiber-optic networks are known in the prior art. One example is the TeledesicSM TDMA network. This type of multiplexing also provides theoretical spectral efficiency, without the wasteful complex capacity variability of CDMA networks.
However, packet-based TDMA satellite-cellular technology also requires large blocks of contiguous frequencies, blocks that are only available in the weather-sensitive gigahertz frequencies at the high end of the spectrum. Also, TDMA traffic is highly sensitive to time jitter, which necessitates the use of fixed tiling and complex, expensive, error prone xe2x80x9csteerable-beamxe2x80x9d satellite equipment, to protect the continuity of each link""s time base.
Thus, a CDMA satellite network has distinct advantages over TDMA satellite networks, if the set of peculiarly troublesome CDMA link-allocation problems inherent in such network operations are solved.
Cell Size Parameters
FDMA-type ground-cellular networks are organized into individual xe2x80x9ccellsxe2x80x9d. Each cell in a ground-cellular network has a respective administrative pilot-signal, and a cell radius that is defined, operationally, by the power of the pilot signal transmitted by the cell""s terrestrial base station. The coverage area for a given satellite is its xe2x80x9cfootprintxe2x80x9d, i.e., the projection of its beams onto the earth""s surface. As is well known, the extent of the area covered by a satellite""s footprint is determined by the satellite""s height above the earth and the geometry of the satellite""s transmitting antenna.
The size of cells in FDMA ground-cellular networks is also limited, as a practical matter, by the power that mobile terminals need to transmit back to a base station, particularly the transmitters of hand-held cellular phones which are limited in power by health and safety concerns as well as battery power. In satellite cellular networks, the limited power of hand-held units requires the use of transiting, low-earth-orbit (LEO) satellites, rather than the geostationary satellites (i.e., satellites that can be conveniently fixed at a point in space relative to a point on the earth).
Because LEO satellites are not geostationary, these satellites can move into and/or out of range during a call. Thus an overlap between the areas served by respective satellites that provide the same channel is desirable. Link diversity (i.e., more than one beam or satellite having the channel assigned to a given call) is needed to prevent interruption of the call by a frequency change when the satellite transponder previously being used by that call moves out of range.
Tiling (i.e., the assignment of a satellite channel to a geographically-defined area similar to the xe2x80x9ccellxe2x80x9d in FDMA ground-cellular networks) permits multiple LEO satellites to provide a given channel to a given user, rather than forcing the user to change channels when changing beams or satellites. This is particularly advantageous for LEO satellite networks.
In the prior art, one TDMA network, for example, proposes that rows of constant-spaced tiles be aligned along the earth""s latitudes. However, this rigid pattern results in some areas being underserved while others nearby have excess capacity, and satellite diversity is not provided. Tiling, however, provides a convenient way of controlling channel-frequency reuse that is independent of LEO satellites"" relative motion. By defining the diameter of each tile relative to the minimum beam width, tiling can also be used to set a minimum separation distance for channel reuse, in terms of the assignment of a channel to particular tiles having a fixed geometric relation to each other on the earth""s surface.
Geographic Separation and Interference
In either satellite-cellular or ground-cellular networks, more user traffic can be accommodated if geographically-smaller cells are used. However, each nearby cell in an FDMA ground-cellular network uses a different channel frequency to avoid co-channel interference typically referred to as xe2x80x9ccrosstalkxe2x80x9d. FDMA ground cellular networks xe2x80x9creusexe2x80x9d frequencies by assigning them to multiple cells to accommodate additional user circuits. These cells can only reuse frequencies if they are at least some geographical distance away from other cells using that same frequency, to avoid co-channel interference, as noted by William C. Y. Lee, in a publication entitled Mobile Communications Design Fundamentals, Wiley and Sons, 1993.
The signal-to-noise interference ratio (SNIR) of a satellite-cellular network is a function of the power of adjacent beams, the power of adjacent channel frequencies and the power of the same channel frequency when it is reused by nearby terminals. The permissible range of power-flux density of satellite-related transmissions, as measured at the earth""s surface, is defined by various standards, as for example the international standard ITU RR-2566.
Channel-Allocation Parameters
In hybrid FDMA/CDMA ground-cellular networks, the strength of a set of secondary CDMA-pilot signals for each link may also limit the maximum number and geographical radius of their respective cells. For LEO satellite-cellular networks, the strength of FDMA/CDMA pilot signals in the forward link is determined by propagation losses between the satellite and the gateway, and by the size of the beam footprint (i.e., the moving area covered by a beam""s projection onto the earth""s surface). Each satellite can provide multiple FDMA channel frequencies, and multiple CDMA links are available for each FDMA channel. However, each forward link provided by the satellite is defined by both an FDMA carrier frequency and a CDMA pilot signal produced by respective signal generators on board the satellite, and each such signal generator draws battery power.
Thus, for satellite-cellular networks, the number of forward links in each channel is a critically important operational constraint. For low cost satellites, in particular, the instantaneous power supplied to each satellite beam is an important operational constraint.
Channel and Link Diversity Policies
The amount of power needed to support the individual links required by user demand is also affected by the partitioning protocol used by the FDMA channels: a complete partitioning (CP) between gateways assures fast access and less co-channel interference, by reserving individual frequencies for the private use of one base station/gateway and its own particular group of user terminals for a particular time period. Alternatively, FDMA channels can be shared by multiple base stations/gateways and their respective user terminals, either completely (SC) or up to some cutoff (CO), to conserve spectrum and reduce the number of FDMA beacons and CDMA pilot frequencies needed.
In SC, CP/SC and CO networks, one call from a given cell may simultaneously be assigned to the same frequency on multiple satellites, to provide xe2x80x9clink diversityxe2x80x9d. Satellite and link diversity can increase the number of hard handoffs (i.e., the carrier frequency changes that occur during a call). In general, hard handoffs occur in cellular networks when mobile users move into an adjacent cell""s coverage area. In a LEO satellite-cellular network, they also occur when a satellite""s coverage area moves away from a user, even when the user is stationary. Thus hard hand-offs can happen much more often in satellite-cellular networks. For example, according to AMPs (the analog cellular network standard), as a user passes from one cell to an adjacent cell, a hard handoff must occur.
In satellite-cellular networks, the channel used by a mobile unit may suddenly become unavailable, even if the mobile unit has not moved, because the area where the mobile unit is located is now illuminated by a different beam from the same satellite, or even by a beam from a different satellite. Thus handoffs may occur more often in satellite-cellular networks, occurring even when the location of the user terminal is stationary.
New calls can be placed using any carrier frequency. Ground-cellular mobile users initially find and select a cellular channel by searching for the strongest administrative pilot signals sent by nearby gateways as beacons. After that, as the mobile terminal passes into the area served by a different gateway, users may be explicitly directed by a control message on the administrative channel or by a portion of the channel being received to change to a specific new channel.
Thereafter, hard-handoffs from the initial carrier frequency may produce momentary outages or xe2x80x9cdroppedxe2x80x9d calls. Regardless of the cause, if a user terminal must change channel frequencies while a call is in progress, noise produced by that change compromises the quality of that call connection. Channel changes often affect circuit quality by causing a xe2x80x9cclickxe2x80x9d noise or, worse, an unworkable frame error rate on a link causing the call to be dropped, either because the error rate produces excess acquisition delay, or because an excessive SNIR after acquisition has triggered a reassignment of the link by the network.
In either ground-cellular or satellite-cellular networks, if a user terminal is directed to change channels while a call is in progress, additional noise produced by that change may compromise the quality of that call circuit. Channel quality during a call is also affected by co-channel interference and self interference, fading, shadowing and signal reflection, as well as by hard and soft handoffs.
Channel allocation spectral efficiency in hybrid FDMA/CDMA ground-cellular networks is affected by the SNIR quality of the individual CDMA links within each FDMA channel, as well as the assignment of FDMA channels to users and base stations or gateways. Thus, for efficient network operation, a channel-allocation system for satellite-cellular networks must provide allocation plans that balance those competing requirements of forward-link quality and capacity against satellite power constraints.
In multiple-satellite networks, FDMA/CDMA link allocation is further complicated by the need to dynamically assign channels so that the assignment of channels to gateways is coordinated with satellites"" movement as well as that of mobile users. To avoid this further complication, computers on board a conventional satellite system use steerable beams, ATM-type routing switches, 64 on-board modems, etc. and satellite-to-satellite communication links to reduce handoffs and simplify allocation of their TDMA links. However, this type of on-board control system is expensive, complex, and hence, less reliable. Also, steerable beams require a wasteful, invariant tiling of the earth""s surface to maintain consistent beam registration.
Known ground-cellular channel allocation strategies do not provide satisfactory channel capacity and channel quality for satellite-cellular FDMA/CDMA networks. Any xe2x80x9ccontrolxe2x80x9d action must affect the network in time to counter a disturbance. If the action is not timely, it is not effective. However, the computations required by existing channel-allocation strategies for minimizing satellite self-interference and conserving satellite battery power are too cumbersome for their results to be timely.
Also, satellite self-interference and the need to conserve satellite power both impose constraints on satellite networks"" operations that are very different from those encountered in designing ground-cellular networks.
The xe2x80x9cnoisexe2x80x9d that makes up a satellite-cellular network""s SNIR is generally thermal or external noise. The interference caused by CDMA signals from other satellites using the same channel is co-channel interference. Interference that is caused by the satellite""s other beams that share a FDMA channel frequency (i.e., other links in the same channel of the same beam) and xe2x80x9cside-lobesxe2x80x9d of the beams of the multi-beam on-board antennas used by FDMA/CDMA satellites, is generally referred to as xe2x80x9cself-interferencexe2x80x9d and is included in the SNIR.
Co-channel interference arises when ground cellular FDMA networks assign a channel frequency to multiple base stations for frequency xe2x80x9creusexe2x80x9d by separate calls to improve their spectral efficiency. However, the assignment of one call to the same frequency at multiple adjacent base stations achieves xe2x80x9clink diversityxe2x80x9d that reduces hard handoffs.
This xe2x80x9clink diversityxe2x80x9d among two or more base stations can also improve the signals SNIR performance by eliminating the effects of the multipath reflections caused by buildings and hills in a particular physical signal path.
When using xe2x80x9ccoherent combiningxe2x80x9d, ground cellular networks can assign one call to the same frequency at multiple adjacent base stations without causing co-channel interference, because these signals can be summed by the gateway. xe2x80x9cCoherent combiningxe2x80x9d of diverse links can also eliminate blockage and improve a signal""s SNIR performance by block-interleaving the phase-matched signals from two or more satellites.
Although xe2x80x9clink-diversityxe2x80x9d has been known and used for some time, the ability to allocate one link to two transiting, potentially-interfering satellites (i.e., the diversity that makes coherent combining possible) is not known in previous cellular-network channel-allocation systems. Instead, satellite-cellular networks typically use only one source for each link in the network to reduce self interference.
Slow Fluctuations and Sudden Infeasibility
In a ground-cellular network, the greater the power of the cell""s pilot signal, the larger the coverage area of that cell is, and the number users within the cell is limited only by transmitter wattage and the available spectrum. However, when a satellite-cellular network is operating at full-traffic load, available battery power is the most critical consideration for cost effective satellites. Thus, the assignment of the satellite""s forward, downlink channels (those most directly affecting its battery""s condition) is definitive for the remainder of a satellite-cellular network""s links.
Channel allocation must also balance battery power demand over time to maintain the maximum on-board channel capacity in a satellite-cellular network. That is, whenever one channel reaches an operating limit, such as a thermal or self-interference SNIR constraint, or a battery-power limit, then all channels on board that satellite should be operating close to that same limit, to maximize the network""s capacity and stability.
However, slow power fluctuations in an individual satellites"" signals, typically changes lasting several minutes, are characteristic of satellite-cellular networks even when user traffic volume is constant. Because they are slower than 1 Hz, principally caused by the variable elevation of the satellite above the horizon over time, these fluctuations in signal strength can often be countered by tactical power-control compensation. However, the magnitude and duration of these fluctuations may exceed the on-board battery-power that is available for such compensation.
Fixed-channel allocations may consider the maximum volume of user-traffic anticipated at locations in the service area, and the geometry of the satellite beams. However, when user-traffic volume is large, conventional allocation strategies may produce suboptimal, wasteful channel assignments, because they make inflexible assumptions. In particular, employing an arbitrary, fixed value for a satellite""s maximum usable on-board power can unnecessarily limit the number of links available in each channel it transmits.
Analytic models that address the need to conserve satellite power in making channel allocations have been proposed. Examples of the prior art in this area are: Gagliardi, Satellite Communications, Lifetime Learning Publications, 1984; and J. Zander, H. Eriksson, xe2x80x9cAsymptotic Bounds on the Performance of a Class of Dynamic Channel Assignment Algorithmsxe2x80x9d, IEEE Journal of Selected Areas in Communications, August 1993. However, these models are oversimplified. They generally do not take satellite orbital dynamics into account, nor are they applicable to gateways that only communicate through an operational control center. Furthermore, they are designed for multiplexing individual user circuits within a single bandwidth, rather than the multiple FDMA bandwidths used by hybrid FDMA/CDMA networks.
Prior art constrained optimization methods applicable to allocation problems include Mixed Integer Programming, Greedy-Algorithm, and Graph Theoretic techniques.
Mixed-Integer Programming (MIP) methods can be used to determine a channel allocation for a particular fixed point in time that minimizes the number of channels, thus minimizing power consumed by pilot signals. However, the MIP model operates in one way for a completely-shared strategy, and another for a completely-partitioned strategy. For a completely-shared strategy, integer variables are used to assign specific channels. For a completely-partitioned strategy, integer variables assign particular channels to particular gateways. However, this either/or dichotomy between completely-shared channels and completely-partitioned channels makes it inapplicable to many types of hybrid networks.
Also, the MIP model assumes that a network""s channel capacity is both constant and known, because it is a parameter value at that fixed point in time, in the model. However, since CDMA channels are xe2x80x9csoftxe2x80x9d, the assumption that a given number of channels is always available makes it unworkable for CDMA networks.
In contrast, xe2x80x9cGreedy-algorithmxe2x80x9d techniques first solve the allocation problem by assuming an infinite supply of channels. The mapping of call traffic that is produced by that initial assumption is then examined and simplified using some heuristic to reduce it to the actual number of channels available. Monte Carlo simulation techniques often provide the heuristic simplification. Greedy algorithm solutions of the allocation problem are also not practical for large, complex multiple-satellite cellular networks because of the computational burden they impose on the network. Greedy algorithms tend to be quite efficient (i.e., minimum Spanning Tree algorithms run in O(e log e).
Graph-theoretic techniques, such as xe2x80x9cClique Packingxe2x80x9d can provide close-to-optimal solutions, if traffic is constant or, at least, fully-determinable. However, these techniques are often difficult to scale to real-world traffic conditions, because they are statically predictable, but non-stationary. Also, real-world traffic conditions are not constant. In fact, they are not even temporarily stationary. Allocations using graph theoretic techniques also impose an unacceptably onerous computational burden.
In view of the limitations of the prior art, it is an object of the present invention to provide a channel-frequency allocation system that permits hybrid partitioning of both satellite and link diversity.
It is another object of the invention to optimize the trade-offs related to the conflicting costs and advantages of hard handoffs, diversity, and self-interference.
It is a further object of the invention to optimize satellite-cellular service quality and availability while minimizing reductions in network capacity from misallocated channel frequencies.
Yet another object of the invention is to reduce uncertainty about the usable capacity of an FDMA channel, thereby optimizing spectral efficiency of FDMA/CDMA networks.
It is a further object of the invention to allocate non-contiguous frequencies in hybrid FDMA/CDMA bandwidths for satellite cellular networks while reducing the number of hard handoffs.
It is a further object of this invention to allocate channels in a hybrid/CDMA system so as to efficiently assign gateways and their associated mobile user terminals to channels in a multiple satellite system.
It is another object of the invention to assign channels that are coordinated between gateways.
A satellite communications system operative with at least one existing terrestrial communication system for carrying traffic is described. The system comprises a plurality of satellites in earth orbits, each of the satellites radiating one or more forward links containing traffic to one or more terrestrial users, each forward link of each of the satellites having a maximum radiation limit and a frequency channel. One or more of the terrestrial users is capable of concurrently receiving at least two of the forward links, the concurrently received two forward links redundantly containing the traffic. The system also has one or more terrestrial gateways, the gateways being bidirectionally linked to one or more satellites of the plurality of satellites for carrying the traffic. The system further includes a computing center, linked to the gateways, having a frequency allocation function for allocating each operating frequency channel to the satellites using the gateways. The frequency allocation function comprises a user model having a frequency re-use pattern; a channel allocation model for modelling the power allocated to each channel; and a gateway channel model for allocating channels in accordance with the user model and the channel allocation model. The allocation is made for each satellite of the plurality of satellites. The traffic allocation assigns an operating frequency for each of the one or more links in each satellite of the plurality of satellites.